Modelo de bloque estocástico

El modelo de bloques estocásticos es un modelo generativo para grafos aleatorios. Este modelo tiende a producir grafos que contienen comunidades, subconjuntos de nodos caracterizados por estar conectados entre sí con densidades de arista particulares. Por ejemplo, los bordes pueden ser más comunes dentro de las comunidades que entre comunidades distintaas. Su formulación matemática fue introducida por primera vez en 1983 en el campo de las redes sociales por Holland et al. El modelo de bloque estocástico es importante en estadística, aprendizaje automático y ciencia de redes, donde sirve como un punto de referencia útil para la tarea de recuperar la estructura de la comunidad en datos de grafos.

Definición

El modelo de bloque estocástico toma los siguientes parámetros:

• El número $n$ de vértices;
• una partición del conjunto de vértices $\{1,\ldots ,n\}$ en subconjuntos disjuntos $C_{1},\ldots ,C_{r}$, llamados comunidades ;
• una matriz $P$ de dimensiones $r\times r$ simétrica con probabilidades de arista.

Luego, el conjunto de aristas se muestrea al azar de la siguiente manera: dos vértices cualesquiera $u\in C_{i}$ y $v\in C_{j}$ están conectados por una arista con probabilidad $P_{ij}$ . Un problema de ejemplo es: dado un grafo con $n$ vértices, donde los bordes se muestrean como se describe, recuperar los grupos $C_{1},\ldots ,C_{r}$ .

Casos especiales

Si la matriz de probabilidad es constante, en el sentido de que $P_{ij}=p$ para todas las parejas $i,j$, entonces el resultado es el modelo Erdős-Rényi $G(n,p)$ . Este caso es degenerado, la partición en comunidades se vuelve irrelevante, pero ilustra una estrecha relación con el modelo Erdős-Rényi.

El modelo de partición plantada es el caso especial de que los valores de la matriz de probabilidad $P$ son una constante $p$ en la diagonal y otra constante $q$ fuera de la diagonal. Así dos vértices dentro de la misma comunidad comparten una arista con probabilidad $p$, mientras que dos vértices en diferentes comunidades comparten una arista con probabilidad $q$ . A veces, este modelo restringido se denomina modelo de bloques estocásticos. El caso donde $p>q$ se llama un modelo surtido, mientras que el caso $p<q$ se llama modelo no surtido.

Volviendo al modelo general de bloques estocásticos, un modelo se llama fuertemente surtido si $P_{ii}>P_{jk}$ siempre que $j\neq k$ : todas las entradas diagonales dominan todas las entradas fuera de la diagonal. Un modelo se llama débilmente surtido si $P_{ii}>P_{ij}$ siempre que $i\neq j$ : solo se requiere que cada entrada diagonal domine el resto de su propia fila y columna.​ Existen formas desordenadas de esta terminología, al invertir todas las desigualdades. Para algunos algoritmos, la recuperación puede ser más fácil para los modelos de bloques con condiciones surtidas o no surtidas de esta forma.​

Tareas estadísticas típicas

Gran parte de la literatura sobre detección algorítmica de comunidades aborda tres tareas estadísticas: detección, recuperación parcial y recuperación exacta.

Detección

El objetivo de los algoritmos de detección es simplemente determinar, dado un grafo de muestra, si el grafo tiene una estructura de comunidad latente. Más precisamente, se podría generar un grafo, con alguna probabilidad previa conocida, a partir de un modelo de bloque estocástico conocido y, de lo contrario, a partir de un modelo Erdos-Renyi similar. La tarea algorítmica es identificar correctamente cuál de estos dos modelos subyacentes generaron el grafo.​

Recuperación parcial

En la recuperación parcial, el objetivo es determinar aproximadamente la partición latente en las comunidades, en el sentido de encontrar una partición que se correlacione con la partición real significativamente mejor que una suposición aleatoria.​

Recuperación exacta

En recuperación exacta, el objetivo es recuperar exactamente la partición latente en comunidades del grafo. El tamaño de la comunidad y la matriz de probabilidad pueden ser conocidos​ o desconocidos.​

Límites inferiores estadísticos y comportamiento de umbral

Los modelos de bloques estocásticos exhiben un efecto de umbral agudo que recuerda a los umbrales de percolación.​ Supongamos que permitimos que el tamaño $n$ del grafo crezca, manteniendo los tamaños de las comunidades en proporciones fijas. Si la matriz de probabilidad permanece fija, tareas como la recuperación parcial y exacta se vuelven realizables para todos los ajustes de parámetros no degenerados. Sin embargo, si reducimos la matriz de probabilidad a una tasa adecuada a medida que $n$ aumenta, observamos una transición de fase brusca: para ciertos ajustes de los parámetros, será posible lograr la recuperación con una probabilidad que tiende a 1, mientras que en el lado opuesto del umbral del parámetro, la probabilidad de recuperación tiende a 0 sin importar qué algoritmo se use.

Para la recuperación parcial, la escala apropiada consiste en que tomemos $P_{ij}={\tilde {P}}_{ij}/n$ para ${\tilde {P}}$ fijo, resultando en grafos de grado promedio constante. En el caso de dos comunidades de igual tamaño, en el modelo de partición plantada sorteada con matriz de probabilidad

$$P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),$$

la recuperación parcial es realizable con probabilidad $1-o(1)$ siempre y cuando $({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})$, mientras que cualquier estimador falla realizando una recuperación parcial con probabilidad $1-o(1)$ siempre y cuando $({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})$ .

Para una recuperación exacta, la escala apropiada es tomar $P_{ij}={\tilde {P}}_{ij}\log n/n$, dando como resultado grafos de grado medio logarítmico. Aquí existe un umbral similar: para el modelo de partición plantada surtido con $r$ comunidades de igual tamaño, el umbral se encuentra tan cerca como ${\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}$ . De hecho, el umbral de recuperación exacta se conoce para el modelo de bloque estocástico totalmente general.

Algoritmos

En principio, la recuperación exacta se puede resolver en su rango factible utilizando la máxima verosimilitud, pero esto equivale a resolver un problema de corte restringido o regularizado, como una bisección mínima que normalmente es NP-completa . Por lo tanto, ningún algoritmo eficiente conocido calculará correctamente la estimación de máxima verosimilitud en el peor de los casos.

Sin embargo, una amplia variedad de algoritmos funcionan bien en el caso promedio, y se han probado muchas garantías de rendimiento de alta probabilidad para algoritmos de recuperación tanto parcial como exacta. Los algoritmos exitosos incluyen el agrupamiento espectral de los vértices, programación semidefinida, formas de propagación de creencias, y detección comunitaria entre otros.

Variantes

Existen varias variantes del modelo. Un ajuste menor asigna los vértices a las comunidades al azar, de acuerdo con una distribución categórica, en lugar de una partición fija. Las variantes más significativas incluyen el modelo de bloques estocásticos de grado corregido, el modelo de bloques estocásticos jerárquicos, el modelo de bloques geométricos, el modelo de bloques censurados y el modelo de bloques de membresía mixta.

Modelos de tema

Se ha reconocido que el modelo de bloque estocástico es un modelo temático en redes bipartitas.​ En una red de documentos y palabras, el modelo de bloque estocástico puede identificar temas: grupo de palabras con un significado similar.

Extensiones a grafos con signo

Los grafos con signo permiten relaciones tanto favorables como adversas y sirven como una opción de modelo común para varias aplicaciones de análisis de datos, por ejemplo, agrupación de correlación. El modelo de bloques estocásticos puede extenderse de manera trivial a grafos con signo asignando pesos de arista positivos y negativos, o de manera equivalente, utilizando una diferencia de matrices de adyacencia de dos modelos de bloques estocásticos.​

DARPA/MIT/AWS Graph Challenge: transmisión de partición de bloques estocásticos

GraphChallenge fomenta los enfoques comunitarios para desarrollar nuevas soluciones para analizar grafos y datos escasos derivados de las redes sociales, fuentes de sensores y datos científicos para permitir que se descubran las relaciones entre eventos a medida que se desarrollan en el campo. La partición de bloques estocásticos en streaming es uno de los desafíos desde 2017. El agrupamiento espectral ha demostrado un rendimiento sobresaliente en comparación con el algoritmo base original e incluso mejorado​, igualando la calidad de los agrupamientos y siendo varios órdenes de magnitud más rápido.​​

Véase también

• Modelado de bloques
• Algoritmo de detección de comunidades de Girvan–Newman —
• Lancichinetti–Fortunato–Radicchi benchmark — para generar redes de referencia con las comunidades